package oj;

import java.util.*;
//前k个高频单词：给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
//返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
public class Solution_692_1 {
    //方法1：使用map
    static class Cmp implements Comparator<Map.Entry<String,Integer>>{
        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            // 按照这样的顺序进行大小的规定 i-2 < love-2 < coding-1 < leetcode-1
            String word1 = o1.getKey();
            int count1 = o1.getValue();

            String word2 = o2.getKey();
            int count2 = o2.getValue();

            if(count1 < count2){
                //o1 : coding-1
                //o2 : i-2
                //o1 > o2
                return 1;
            }else if(count1 > count2){
                //o1 : i-2
                //o2 : coding-1
                //o1 < o2
                return -1;
            }
            //如果 count 相同，那么就比较单词的大小
            return word1.compareTo(word2);
        }
    }

    public static List<String> topKFrequent(String[] words, int k) {
        Map<String,Integer> countMap = new TreeMap<>();
        for(String w : words){
            int count = countMap.getOrDefault(w,0);
            countMap.put(w,count + 1);
        }
        //得到每个单词出现的次数
        //先使用排序来完成
        //List
        //元素  单词-次数      Entry<单词，次数>
        //List<Entry<单词，次数>>  list
        //要排序，意味着元素是具备比较能力的，目前不具备，所以需要用 Comparator
        //默认情况下的排序为升序
        //我们要的是：i-2 < love-2 < coding-1 < leetcode-1
        //键值对的Map
        Set<Map.Entry<String,Integer>> entrySet = countMap.entrySet();
        //将 Set 转换为 List 进行排序
        List<Map.Entry<String,Integer>> list = new ArrayList<>(entrySet);
        //对 list 进行排序
        Cmp comparator = new Cmp();
        Collections.sort(list,comparator);

        List<String> ans = new ArrayList<>();
        for(int i = 0;i < k;i++){
            Map.Entry<String,Integer> entry = list.get(i);
            String word = entry.getKey();
            ans.add(word);
        }
        return ans;
    }
}
